// 求最长递增子序列的个数
// [3, 2, 8, 9, 6, 7, 11, 15]
// 2 5 6 7 11 15
// 贪心算法 + 二分查找 + 前驱节点追溯

//  找更有潜力的，比如2比3小，2后面可以有3，所以以2替换掉3
// 3
// 2
// 28
// 289
// 259
// 256
// 2 5 6 7 11 15(求到的长度一定是对的，顺序不一定对)

// 1. 思路就是当前这一项比我们最后一项大则直接放到末尾
// 2. 如果当前这一项比最后一项小，需要在序列中通过贰分查找找到比当前大的这一项，用他来替换掉
// 3. 最优的情况 就是默认递增

// 37fenzhong
function getSequence(arr) {
  const len = arr.length;
  const result = [0]; // 存索引，默认值是第一个元素的索引
  const p = new Array(len).fill(0); // 最后要标记索引，里面放的东西不用关心，但是要和数组一样长
  let start;
  let end;
  let middle;
  let resultLastIndex;

  for (let i = 0; i < len; i++) {
    let arrI = arr[i];
    if (arrI !== 0) {
      // 因为vue序列中0 意为着需要创建 没有意义
      resultLastIndex = result[result.length - 1];
      // 比较最后一项和当前项的值，如果比最后一项大，则将当前项的索引push进结果集合
      if (arr[resultLastIndex] < arrI) {
        result.push(i);
        p[i] = resultLastIndex; // 当前放到末尾的要记住他前面的那个人是谁
        continue;
      }

      // 这里通过二分查找，在结果集中找到比当前大的值，用当前索引替换掉其索引
      // 递增序列，采用二分查找是最快的
      start = 0;
      end = result.length - 1;
      // start === end的时候就停止了
      while (start < end) {
        middle = ((start + end) / 2) | 0;
        if (arr[result[middle]] < arrI) {
          start = middle + 1;
        } else {
          end = middle;
        }
      }
      console.log(end);
      // 到中间值后，我们需要做替换操作 start|end
      if (arr[result[end] > arrI]) {
        result[end] = i;
        // 修改前驱
        p[i] = result[end - 1];
      }
    }
  }
  console.log(result);

  // 通过最后一项进行回溯
  let i = result.length;
  let last = result[i - 1];
  while (i-- > 0) {
    result[i] = last;
    last = p[last];
  }
  return result;
}

getSequence([3, 2, 8, 9, 5, 6, 7, 11, 15, 4]);
// [1,2]
